package com.myc.subjects.linkedlist;

import com.myc.subjects.utils.LinkedListUtils;

/**
 * LeetCode题号：21
 *
 * 合并两个有序链表
 *
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 *
 * 示例 1：
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 *
 * 示例 2：
 * 输入：l1 = [], l2 = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 *
 * 提示：
 * 两个链表的节点数目范围是 [0, 50]
 * -100 <= Node.val <= 100
 * l1 和 l2 均按 非递减顺序 排列
 */

public class Hebingyouxulianbiao {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(4);
        ListNode listNode2 = new ListNode(3, listNode1);
        ListNode listNode3 = new ListNode(1, listNode2);

        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(2, listNode4);
        ListNode listNode6 = new ListNode(1, listNode5);

        Hebingyouxulianbiao hebingyouxulianbiao = new Hebingyouxulianbiao();
        LinkedListUtils.showLinkedList(hebingyouxulianbiao.mergeTwoLists3(listNode3, listNode6));

    }

    /**
     * 方法一：迭代法
     * 时间复杂度：O(m + n)  m为l1长度，n为l2长度
     * 利用哨兵节点组装结果链表，用一个 while 循环遍历 l1 和 l2 ，l1 更小或者 l2 遍历完则取 l1，否则取 l2
     */
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        //定义哨兵节点，用于组装结果链表
        ListNode sentinel = new ListNode(0);
        //定义当前节点负责拼接结果链表
        ListNode curr = sentinel;

        while (l1 != null || l2 != null) {//循环的条件l1或者l2有一个没有遍历完就会继续遍历
            //l1不为空是前提，同时 l2 为空或者 l1 的值小于 l2 的值则curr拼上l1的节点
            if (l1 != null && (l2 == null || l1.val <= l2.val)) {
                curr.next = l1;
                l1 = l1.next;
            } else {//其他情况都拼上 l2 的节点
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;//curr后移
        }
        return sentinel.next;
    }

    /**
     * 方法二：递归法
     * 时间复杂度：O(m+n)  m为l1长度，n为l2长度
     * 参照之前总结的递归方法的几个步骤列出的递归方法
     */
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        ////1.处理特殊情况，同时也是递归终止条件
        if(l1 == null && l2 == null) return null;

        ListNode result = null;//定义结果
        //2.准备参数
        if(l1 != null && (l2 == null || l1.val <= l2.val)){
            result = l1;
            l1 = l1.next;
        }else{
            result = l2;
            l2 = l2.next;
        }
        //3.将准备好的参数带入递归方法
        result.next = mergeTwoLists2(l1, l2);
        //4.处理递归结果，并返回
        return result;
    }

    /**
     * 方法三：递归法优化
     * 时间复杂度：O(m+n)  m为l1长度，n为l2长度
     * 在方法二的基础上，修改边界条件为，有一个参数链表为空，则终止递归，再拼上另一个链表。
     * 调用递归时，l1和l2更小的情况分开调用，这样就不需要result来拼接结果链表了
     */
    public ListNode mergeTwoLists3(ListNode l1, ListNode l2){
        //边界条件改为，有一个参数链表为空，则终止递归，再拼上另一个链表
        if(l1 == null) return l2;
        if(l2 == null) return l1;

        if(l1.val < l2.val){
            l1.next = mergeTwoLists3(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists3(l1, l2.next);
            return l2;
        }
    }

    //官方题解
    //方法一：迭代
    public ListNode mergeTwoListsOfficial1(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoListsOfficial1(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoListsOfficial1(l1, l2.next);
            return l2;
        }
    }

    //方法二：递归
    public ListNode mergeTwoListsOfficial2(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }

}

/**
 * 总结：
 * 1.关于链表的题目很多都可以用迭代和递归两种方法来解题
 * 2.善于利用哨兵节点解决链表的零界问题
 */
